The present invention relates to a method for computer-aided identification of the child octants of a parent octant, which are intersected by a beam, in an octree data structure. The invention relates in addition also to methods which are described subsequently in more detail, said methods being based on the method according to the invention and using it in different technical fields, to the use of such methods and also to a computer system which is configured to achieve the method according to the invention.
An octree (lat. oct “8” and English tree) is a data structure known from information technology. An octree can be regarded as a tree with a root, the nodes of which respectively have either exactly 8 direct successors or no successor at all. Octrees are used mainly in computer graphics in order to subdivide three-dimensional data sets hierarchically. The root of the octree thereby represents all the data, each other node represents an octant of the data of its direct predecessor. The root or a predecessor are subsequently also termed parent octant alternatively. The subsequent nodes of a predecessor are subsequently termed also child octants. Each parent octant has hence either exactly 8 child octants or no child octant. Subsequently, the term octant or node is used synonymously or alternatively to the information which can be stored in such a node within the framework of the octree data structure. Thus, for example each parent octant of the special expression min-max-octree can contain the minimum and the maximum of the successive partial tree (i.e. of the 8 assigned child octants), which enables efficient search algorithms. The individual data values which are stored in the individual nodes or octants correspond thereby to values, such as for example real numbers, which can be compared with each other with a size relation. Thus the individual stored values can represent for example the density of a physical medium.
The most frequent application of an octree, as used in the invention, relates to the uniform division of a cube-shaped data set: the root (or that parent octant which is highest in the hierarchy) is subdivided into 8 smaller cubes, the child octants. Each child octant is then divided in turn into a further 8 grandchild octants etc. The subdivision of a partial cube ends hereby when no further division is possible or if no further division is necessary.
The individual children volumes produced by the division (by means of corresponding dividing planes which are disposed for example perpendicular to the individual coordinate axes x, y and z of a Cartesian coordinate system) need not however be cube-shaped but can also in general have a cuboid configuration. A subdivision of the volumes into parts of an unequal size is also possible.